class Solution {
    public boolean exist(char[][] board, String word) {
        int i = 0, j = 0;
        int ret = 0;
        //几行
        int rowlen = board.length;
        //几列
        int comlen = board[0].length;
        //先找到第一个字母的位置
        for(i = 0;i<rowlen;i++) {
            for(j = 0;j<comlen;j++) {
                if(dfs(board,word,i,j,ret)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word,int i,int j, int ret) {
        if(i<0||j<0||i>board.length-1||j>board[0].length-1||board[i][j]!=word.charAt(ret)) {
            return false;
        }
        if(word.length() - 1 == ret) {
            return true;
        }
        board[i][j] = '\0';
        boolean res = dfs(board,word,i-1,j,ret+1) || dfs(board,word,i+1,j,ret+1) 
        || dfs(board,word,i,j-1,ret+1) || dfs(board,word,i,j+1,ret+1);
        board[i][j] = word.charAt(ret);
        return res;

    }
}